#include <stdio.h>
#include <stdlib.h>

void sort(int* array, int nCnt)
{
    int* lpTmp = (int*)malloc(sizeof(int) * nCnt);
    if (!lpTmp) return;

    int nHead = 0;
    int nTail = 0;
    int k;

    lpTmp[0] = array[0];
    for (int i = 1; i < nCnt; i++)
    {
        if (array[i] < lpTmp[nHead])
        {
            nHead = (nHead - 1 + nCnt) % nCnt;
            lpTmp[nHead] = array[i];
        }
        else if (array[i] > lpTmp[nTail])
        {
            nTail++;
            lpTmp[nTail] = array[i];
        }
        else
        {
            nTail++;
            lpTmp[nTail] = lpTmp[nTail - 1];

            for (k = nTail - 1; lpTmp[(k - 1 + nCnt) % nCnt] > array[i]; k = (k - 1 + nCnt) % nCnt)
                lpTmp[k] = lpTmp[(k - 1 + nCnt) % nCnt];

            lpTmp[k] = array[i];
        }
    }

    for (int i = 0; i < nCnt; i++)
    {
        array[i] = lpTmp[nHead];
        nHead = (nHead + 1) % nCnt;
    }

    free(lpTmp);
}

int main()
{
    int array[9] = { 2,8,5,1,3,11,7,2,6 };

    sort(array, sizeof(array) / sizeof(int));

    for (unsigned int i = 0; i < (sizeof(array) / sizeof(int)); ++i)
        printf("%d ", array[i]);
    puts("");

    return 0;
}